#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct QNode
{
    int data;
    struct QNode *next;
} QNode, *QueuePtr;

typedef struct
{
    QueuePtr front; // 队头指针（直接指向第一个元素）
    QueuePtr rear;  // 队尾指针（指向最后一个元素）
} LinkQueue;

// 1. 初始化队列（不带头结点）
void InitQueue(LinkQueue &Q)
{
    Q.front = Q.rear = NULL; // 两个指针都初始化为NULL
}

// 2. 销毁队列
void DestroyQueue(LinkQueue &Q)
{
    while (Q.front)
    {
        QueuePtr temp = Q.front;
        Q.front = Q.front->next;
        free(temp);
    }
    Q.rear = NULL; // 避免野指针
}

// 3. 入队操作（队尾插入）
bool EnQueue(LinkQueue &Q, int x)
{
    QueuePtr newNode = (QueuePtr)malloc(sizeof(QNode));
    if (!newNode)
    {
        printf("Memory allocation failed!\n");
        return false;
    }
    newNode->data = x;
    newNode->next = NULL;

    if (Q.rear == NULL)
    { // 空队列特殊处理
        Q.front = Q.rear = newNode;
    }
    else
    {
        Q.rear->next = newNode; // 链接新结点
        Q.rear = newNode;       // 更新队尾指针
    }
    return true;
}

// 4. 出队操作（队头删除）
bool DeQueue(LinkQueue &Q, int &x)
{
    if (Q.front == NULL)
    { // 队空判断
        printf("Queue is empty!\n");
        return false;
    }

    QueuePtr temp = Q.front;
    x = temp->data;
    Q.front = Q.front->next; // 移动队头指针

    if (Q.front == NULL)
    {                  // 如果出队后队列为空
        Q.rear = NULL; // 队尾指针也要置空
    }

    free(temp); // 释放原队头结点
    return true;
}

// 5. 获取队头元素
bool GetHead(LinkQueue Q, int &x)
{
    if (Q.front == NULL)
    { // 队空判断
        printf("Queue is empty!\n");
        return false;
    }
    x = Q.front->data;
    return true;
}

// 6. 获取队尾元素
bool GetTail(LinkQueue Q, int &x)
{
    if (Q.rear == NULL)
    { // 队空判断
        printf("Queue is empty!\n");
        return false;
    }
    x = Q.rear->data;
    return true;
}

// 7. 判空操作
bool IsEmpty(LinkQueue Q)
{
    return (Q.front == NULL);
}

// 8. 判满操作（链式队列理论上不会满）
bool IsFull(LinkQueue Q)
{
    return false; // 除非内存耗尽
}

// 打印队列内容（队头到队尾）
void PrintQueue(LinkQueue Q)
{
    if (IsEmpty(Q))
    {
        printf("Queue is empty\n");
        return;
    }

    printf("Queue [front->rear]: ");
    QueuePtr p = Q.front;
    while (p)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

int main()
{
    LinkQueue Q;
    InitQueue(Q); // 初始化队列

    // 入队操作
    EnQueue(Q, 10);
    EnQueue(Q, 20);
    EnQueue(Q, 30);
    PrintQueue(Q); // Queue [front->rear]: 10 20 30

    // 获取队头和队尾
    int head, tail;
    GetHead(Q, head);
    GetTail(Q, tail);
    printf("Head: %d, Tail: %d\n", head, tail); // Head: 10, Tail: 30

    // 出队操作
    int dequeued;
    DeQueue(Q, dequeued);
    printf("Dequeued: %d\n", dequeued); // Dequeued: 10
    PrintQueue(Q);                      // Queue [front->rear]: 20 30

    // 判空和判满测试
    printf("Is empty? %s\n", IsEmpty(Q) ? "true" : "false");
    printf("Is full? %s\n", IsFull(Q) ? "true" : "false");

    // 队列空测试
    printf("Testing queue empty:\n");
    while (DeQueue(Q, dequeued))
    {
        printf("Dequeued: %d\n", dequeued);
    }

    // 打印空队列
    PrintQueue(Q);
    printf("Is empty? %s\n", IsEmpty(Q) ? "true" : "false");

    DestroyQueue(Q); // 销毁队列
    return 0;
}